package com.fanshuai.sort;

import java.util.Arrays;

public class SingleSort {
    /**
     * 冒泡排序  每次循环，将最大的元素排到最后
     * @param s
     */
    public static void bubbleSort(int[] s) {
        int len = s.length;

        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (s[j] > s[j + 1]) {
                    swap(s, j, j + 1);
                }
            }
        }
    }

    /**
     * 沉底排序，每次循环将最小的元素排到最前
     * @param a
     */
    public static void bubbleSortReverse(int[] a) {
        int len = a.length;
        for (int i = 0; i < len; i++) {
            for (int j = len - 1; j > i; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, j, j - 1);
                }
            }
        }
    }

    /**
     * 简单选择排序  每次选取最小元素，交换位置
     * @param a
     */
    public static void selectionSort(int[] a) {
        int len = a.length;
        for (int i = 0; i < len - 1; i++) {
            int k = i;
            for (int j = i + 1; j < len; j++) {
                if (a[j] < a[k]) {
                    k = j;
                }
            }

            if (i != k) {
                swap(a, i, k);
            }
        }
    }

    /**
     * 插入排序  i位置，遍历i-1到0使之有序
     * @param a
     */
    public static void insertionSort(int[] a) {
        int len = a.length;

        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, j, j - 1);
                }
            }
        }
    }

    /**
     * partition操作
     * @param a
     * @param start
     * @param end
     * @return
     */
    private static int partition(int[] a, int start, int end) {
        int base = a[end];
        int left = start - 1;
        int right = end;

        while (true) {
            while (a[++left] < base && left < end) {
                ;
            }
            while (a[--right] > base && right > start) {
                ;
            }
            if (left >= right) {
                break;
            }
            swap(a, left, right);
        }
        swap(a, left, end);
        return left;
    }

    /**
     * 快速排序 每次partition操作，左右子数组有序，然后递归排序
     * @param a
     * @param start
     * @param end
     */
    public static void quickSort(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }

        int partition = partition(a, start, end);

        quickSort(a, start, partition - 1);
        quickSort(a, partition + 1, end);
    }

    /**
     * 快排优化，当子数组小于5时，用插入排序，避免递归太深
     */
    public static int CUTOFF = 5;
    public static void quickSort2(int[] a, int start, int end) {
        if (end - start <= CUTOFF) {
            insertionSort(a, start, end);
            return;
        }

        int partition = partition(a, start, end);
        quickSort2(a, start, partition - 1);
        quickSort2(a, partition + 1, end);
    }

    /**
     * 局部插入排序
     * @param a
     * @param down
     * @param up
     */
    public static void insertionSort(int[] a, int down, int up) {
        for (int i = down + 1; i <= up; i++) {
            for (int j = i; j > down; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }

    public static void mergeSort(int[] a) {
        mergeSort(a, 0, a.length - 1);
    }

    /**
     * 归并排序 思路为：将数组拆分为子数组，子数组排序后，再将2个子数组归并
     * 拆分子数组方式：二分拆分
     * @param a
     * @param start
     * @param end
     */
    public static void mergeSort(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(a, start, mid);
        mergeSort(a, mid + 1, end);

        merge(a, start, mid, end);
    }

    /**
     * 归并排序优化  子数组较小时选择插入排序
     * @param a
     * @param start
     * @param end
     */
    public static void mergeSort2(int[] a, int start, int end) {
        if (end - start >= CUTOFF) {
            insertionSort(a, start, end);
            return;
        }

        int mid = (start + end) / 2;
        mergeSort2(a, start, mid);
        mergeSort2(a, mid + 1, end);

        merge(a, start, mid, end);
    }

    /**
     * 归并数组
     * @param a
     * @param start
     * @param mid
     * @param end
     */
    private static void merge(int[] a, int start, int mid, int end) {
        //辅助数组  完全赋值
        int[] array = new int[a.length];

        int i = start, j = mid + 1;
        int k = start;
        while (i <= mid && j <= end) {
            if (a[i] <= a[j]) { //<=保证稳定排序
                array[k++] = a[i++];
            } else {
                array[k++] = a[j++];
            }
        }
        while (i <= mid) {
            array[k++] = a[i++];
        }
        while (j <= end) {
            array[k++] = a[j++];
        }

        System.arraycopy(array, start, a, start, end - start + 1);
    }

    /**
     * 交换顺序
     * @param a
     * @param i
     * @param j
     */
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 堆下沉操作  构造极大堆
     * @param a  堆 完全二叉树表示
     * @param k  节点索引
     * @param N  最大节点索引
     */
    private static void sink(int[] a, int k, int N) {
        while (2 * k + 1 <= N) {
            int j = 2 * k + 1;
            if (j < N && a[j + 1] > a[j]) {
                j = j + 1;
            }

            if (a[j] > a[k]) {
                swap(a, j, k);
                k = j;
            } else {
                break;
            }
        }
    }

    /**
     * 堆排序
     * @param a
     */
    public static void heapSort(int[] a) {
        //从完全二叉树的非叶子节点遍历，做下沉操作，构造极大堆
        int N = a.length - 1;
        for (int k = (N - 1) / 2; k >= 0; k--) {
            sink(a, k, N);
        }

        //极大堆根节点为最大元素，因此每次将根节点跟最后一个元素交换，同时堆元素数量-1，根节点做sink操作
        while (N > 0) {
            swap(a, 0, N);
            N--;
            sink(a, 0, N);
        }
    }

    public static void main(String[] args) {
        int[] a = {23, 4, 1, 5, 10, 8, 1, 99, 23, 108, 45, 82, 17, 52, 41};
        quickSort(a);
        Arrays.stream(a).forEach(System.out::println);
    }
}
